/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements. See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License. You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package java.util;

/**
 * 链接哈希映射（LinkedHashMap ）是保证迭代顺序的{@link Map}的实现。 所有可选操作均受支持。
 *
 * 所有元素都可以作为键或值，包括空值。
 *
 * 参Entries保存在双向链接列表中。 迭代顺序默认情况下是按键的顺序。
 * 重新插入已经存在的钥匙不会改变顺序。 如果使用三个参数构造函数，
 * 并且 {@code accessOrder} 被指定为{true code}，则迭代将按照访问条目的顺序进行。
 * 访问顺序受 {@code put}, {@code get}, and {@code putAll}操作影响，但不受集合视图操作的影响。
 *
 *注意：{@code LinkedHashMap} 的实现不同步。 如果访问实例的多个线程中的一个线程在结构上修改了地图，
 * 则需要对地图的访问进行同步。
 * 对于插入顺序的实例，结构修改是删除或添加条目的操作。
 * 由于这些方法改变了条目的顺序，
 * 因此访问顺序实例也由{@code put}, {@code get}, and {@code putAll}进行结构修改。
 * 条目value的变化不是结构性变化。
 *
 * 如果映射结构发生变化而迭代器用于遍历元素时，通过调用迭代器方法创建的迭代器可能会抛出一个并发修改异常。
 * 只有迭代器提供的{@code remove}方法允许在迭代期间去除元素。
 * 无法保证此机制在所有非同步并发修改的情况下都能正常工作。 它只能用于调试目的。
 *
 */
public class LinkedHashMap<K, V> extends HashMap<K, V> {

    /**
     * 地图中条目的循环链接列表中的虚拟条目。 第一个真正的入口是header.nxt，
     * 最后一个是header.prv。 如果地图是空的，header.nxt == header && header.prv == header。
     *
     */
    transient LinkedEntry<K, V> header;

    /**
     * 有序访问为true，有序插入为false
     */
    private final boolean accessOrder;

    /**
     * 构造一个新的空链接哈希映射实例。
     */
    public LinkedHashMap() {
        init();
        accessOrder = false;
    }

    /**
     * 用指定的容量构造一个新的链接哈希映射实例。
     *
     * @param initialCapacity 这张地图的初始容量。
     * @throws IllegalArgumentException 当容量小于零时。
     *
     *

     */
    public LinkedHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 用指定的容量和加载因子构造一个新的链接哈希表实例
     *
     * @param initialCapacity 这张地图的初始容量。
     * @param loadFactor 初始加载因子。
     * @throws IllegalArgumentException 当容量小于零或负载因数小于或等于零时
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, false);
    }

    /**
     * 使用指定的容量，加载因子和指定排序行为的标志构造一个新的带有链接哈希映射的实例
     *
     * @param initialCapacity 这个哈希映射的初始容量。
     * @param loadFactor 初始加载因子。
     * @param accessOrder {@code true}是否应该根据上次访问（least-recently-recently访问）完成排序，
     *                                如果排序应该是插入条目的顺序，则为{false}。
     * @throws IllegalArgumentException 当容量小于零或负载因数小于或等于零时。
     */
    public LinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
    }

    /**
     * 构造一个包含指定映射映射的新的{Linked HashMap}实例。 元素的顺序被保留。
     *
     * @param map 要添加的映射。
     */
    public LinkedHashMap(Map<? extends K, ? extends V> map) {
        this(capacityForInitSize(map.size()));
        constructorPutAll(map);
    }

    @Override void init() {
        header = new LinkedEntry<K, V>();
    }

    /**
     * 链接条目将nxt / prv双链接添加到纯哈希映射条目。
     */
    static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
        LinkedEntry<K, V> nxt;
        LinkedEntry<K, V> prv;

        /** Create the header entry */
        LinkedEntry() {
            super(null, null, 0, null);
            nxt = prv = this;
        }

        /** Create a normal entry */
        LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
                    LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }

    /**
     * 返回地图中最老的条目，如果地图为空，则返回{@code null}。
     * @hide
     */
    public Entry<K, V> eldest() {
        LinkedEntry<K, V> eldest = header.nxt;
        return eldest != header ? eldest : null;
    }

    /**
     * 如果指示Evicts最老的条目，则创建一个新条目并将其链接为链接列表的头部。
     * 如果VM的性能允许，此方法应调用构造函数New Entry（而不是复制代码）。
     *
     * 看起来很奇怪，这个方法的任务是将条目添加到散列表（这恰好是我们的超类的省）。
     * 将“下一个”链接传递给此方法并返回新创建的元素的替代方法不起作用！
     * 如果我们删除恰好是新创建的条目的同一个存储桶中的第一个条目的（最老的）条目
     * ，则“下一个”链接将变为无效，并且生成的哈希表损坏。
     *
     */
    @Override void addNewEntry(K key, V value, int hash, int index) {
        LinkedEntry<K, V> header = this.header;

        // 如果指示，请移除最老的条目
        LinkedEntry<K, V> eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                key, value, hash, table[index], header, oldTail);
        table[index] = oldTail.nxt = header.prv = newTail;
    }

    @Override void addNewEntryForNullKey(V value) {
        LinkedEntry<K, V> header = this.header;

        // Remove eldest entry if instructed to do so.
        LinkedEntry<K, V> eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                null, value, 0, null, header, oldTail);
        entryForNullKey = oldTail.nxt = header.prv = newTail;
    }

    /**
     * 如上所述，但没有驱逐。
     */
    @Override HashMapEntry<K, V> constructorNewEntry(
            K key, V value, int hash, HashMapEntry<K, V> next) {
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail
                = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail);
        return oldTail.nxt = header.prv = newTail;
    }

    /**
     * 返回具有指定键的映射的值。
     *
     * @param key the key.
     * @return 如果未找到指定键的映射，则使用指定键映射的值;如果未找到指定键的映射，则返回{null}。
     */
    @Override public V get(Object key) {
        /*
         * 重写此方法可以消除代码复制对超类中多态调用的需求。
         */
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            if (e == null)
                return null;
            if (accessOrder)
                makeTail((LinkedEntry<K, V>) e);
            return e.value;
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                if (accessOrder)
                    makeTail((LinkedEntry<K, V>) e);
                return e.value;
            }
        }
        return null;
    }

    /**
     * 将给定的条目重新链接到列表的尾部。
     * 在访问顺序下，只要Map.get读取预先存在的条目的值或由Map.put修改，就会调用此方法。
     */
    private void makeTail(LinkedEntry<K, V> e) {
        // Unlink e
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;

        // Relink e as tail
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }

    @Override void preModify(HashMapEntry<K, V> e) {
        if (accessOrder) {
            makeTail((LinkedEntry<K, V>) e);
        }
    }

    @Override void postRemove(HashMapEntry<K, V> e) {
        LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
        le.prv.nxt = le.nxt;
        le.nxt.prv = le.prv;
        le.nxt = le.prv = null; // Help the GC (for performance)
    }

    /**
     * This override is done for LinkedHashMap performance: iteration is cheaper
     * via LinkedHashMap nxt links.
     * 这个覆盖是为链接哈希映射表现完成的：迭代通过链接哈希映射nxt链接更便宜。
     */
    @Override public boolean containsValue(Object value) {
        if (value == null) {
            for (LinkedEntry<K, V> header = this.header, e = header.nxt;
                    e != header; e = e.nxt) {
                if (e.value == null) {
                    return true;
                }
            }
            return false;
        }

        // value is non-null
        for (LinkedEntry<K, V> header = this.header, e = header.nxt;
                e != header; e = e.nxt) {
            if (value.equals(e.value)) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        super.clear();

        // Clear all links to help GC
        LinkedEntry<K, V> header = this.header;
        for (LinkedEntry<K, V> e = header.nxt; e != header; ) {
            LinkedEntry<K, V> nxt = e.nxt;
            e.nxt = e.prv = null;
            e = nxt;
        }

        header.nxt = header.prv = header;
    }

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        LinkedEntry<K, V> next = header.nxt;
        LinkedEntry<K, V> lastReturned = null;
        int expectedModCount = modCount;

        public final boolean hasNext() {
            return next != header;
        }

        final LinkedEntry<K, V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            LinkedEntry<K, V> e = next;
            if (e == header)
                throw new NoSuchElementException();
            next = e.nxt;
            return lastReturned = e;
        }

        public final void remove() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (lastReturned == null)
                throw new IllegalStateException();
            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }
    }

    private final class KeyIterator extends LinkedHashIterator<K> {
        public final K next() { return nextEntry().key; }
    }

    private final class ValueIterator extends LinkedHashIterator<V> {
        public final V next() { return nextEntry().value; }
    }

    private final class EntryIterator
            extends LinkedHashIterator<Map.Entry<K, V>> {
        public final Map.Entry<K, V> next() { return nextEntry(); }
    }

    // Override view iterator methods to generate correct iteration order
    @Override Iterator<K> newKeyIterator() {
        return new KeyIterator();
    }
    @Override Iterator<V> newValueIterator() {
        return new ValueIterator();
    }
    @Override Iterator<Map.Entry<K, V>> newEntryIterator() {
        return new EntryIterator();
    }

    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return false;
    }

    private static final long serialVersionUID = 3801124242820219131L;
}
